package com.structure.tree;

import java.util.LinkedList;
import java.util.List;

/**
 * @Author Tanyu
 * @Date 2020/5/26 12:15
 * @Description
 * @Version 1.0
 */
public class TreeClass {

  public static void main(String[] args) {
    TreeClass tree = new TreeClass();
    int[] datas = new int[]{1,2,3,4,5,6,7,8,9};
    List<TreeNode> nodelist = new LinkedList<>();
    tree.creatBinaryTree(datas, nodelist);
    TreeNode root = nodelist.get(0);
    System.out.println("递归先序遍历：");
    tree.preOrderTraversal(root);
  }


  private void creatBinaryTree(int[] datas, List<TreeNode> nodeList ){
    //将数组变成node节点
    for (int nodeindex = 0; nodeindex < datas.length; nodeindex++) {
      TreeNode node=new TreeNode(datas[nodeindex]);
    }

    //给所有父节点设定子节点
    for (int index = 0; index < nodeList.size()/2-1; index++) {
      //编号为n的节点他的左子节点编号为2*n 右子节点编号为2*n+1 但是因为list从0开始编号，所以还要+1
      //这里父节点有1（2,3）,2（4,5）,3（6,7）,4（8,9） 但是最后一个父节点有可能没有右子节点 需要单独处理
      nodeList.get(index).setLeft(nodeList.get(index*2+1));
      nodeList.get(index).setRight(nodeList.get(index*2+2));
    }
    //单独处理最后一个父节点  因为它有可能没有右子节点
    int index = nodeList.size()/2-1;
    nodeList.get(index).setLeft(nodeList.get(index*2+1)); //先设置左子节点
    if(nodeList.size() % 2 == 1){ //如果有奇数个节点，最后一个父节点才有右子节点
      nodeList.get(index).setRight(nodeList.get(index*2+2));
    }
  }

  /**
   * 遍历当前节点的值
   * @param node
   */
  public void checkCurrentNode(TreeNode node){
    System.out.print(node.getVal()+" ");
  }


  public void preOrderTraversal(TreeNode node){
    if (node==null){
      return;//很重要，必须加上 当遇到叶子节点用来停止向下遍历
    }
    checkCurrentNode(node);
    preOrderTraversal(node.getLeft());
    preOrderTraversal(node.getRight());
  }

}
